package swardToOffer.struct_4_tree;

import sun.applet.Main;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

// 面试题34：二叉树中和为某一值的路径
// 题目：输入一棵二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所
// 有路径。从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
// 思路：前序遍历+回溯法，当路径总和==target，将结果添加到路径中
public class PathInTree {
    LinkedList<List<Integer>> res = new LinkedList<>();
    Stack<Integer> path = new Stack<>();
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        recur(root, target);
        return res;
    }
    private void recur(TreeNode root, int target) {
        if (root == null) return;
        path.push(root.val);
        target -= root.val;
        if (root.left == null && root.right == null && target == 0)
            res.add(new LinkedList<>(path));

        recur(root.left, target);
        recur(root.right, target );
        path.pop();
    }

    public static void main(String[] args) {
        PathInTree Main = new PathInTree();

    }

}
